/*
 License
 
 Copyright © 2012 Kevin Kimmich
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights to 
 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 the Software, and to permit persons to whom the Software is furnished to do so, 
 subject to the following conditions:
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
 FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "hash_string_to_pointer.h"

#define HASH_FUNC_LIMIT 0.5
#define DEFAULT_FUNC_BUCKET	100
#define L pthread_mutex_lock(&tptr->mutex)
#define UL pthread_mutex_unlock(&tptr->mutex)
/*
 *  hash() - Hash function returns a hash number for a given key.
 *
 *  tptr: Pointer to a hash table
 *  key: The key to create a hash number for
 */
static int hash_string(const hash_string_t *tptr, const char *key) {
  int i=0;
  int hashvalue;
 
  while (*key != '\0')
    i=(i<<3)+(*key++);
 
  hashvalue = (((i*1103515249)>>tptr->downshift) & tptr->mask);
  if (hashvalue < 0) {
    hashvalue = 0;
  }    
 
  return hashvalue;
}

/*
 *  rebuild_table() - Create new hash table when old one fills up.
 *
 *  tptr: Pointer to a hash table
 */
static void rebuild_func_table(hash_string_t *tptr) {
  hash_string_node_t **old_bucket, *old_hash, *tmp;
  int old_size, h, i;

  old_bucket=tptr->bucket;
  old_size=tptr->size;

    /* make sure we allocate something */
  int buckets = old_size << 1;

  /* initialize the table */
  tptr->entries=0;
  tptr->size=2;
  tptr->mask=1;
  tptr->downshift=29;

  /* ensure buckets is a power of 2 */
  while (tptr->size<buckets) {
    tptr->size<<=1;
    tptr->mask=(tptr->mask<<1)+1;
    tptr->downshift--;
  } /* while */

  /* allocate memory for table */
  tptr->bucket=(hash_string_node_t **) malloc(tptr->size * sizeof(hash_string_node_t *));
  memset(tptr->bucket,0,tptr->size * sizeof(hash_string_node_t *));


  for (i=0; i<old_size; i++) {
    old_hash=old_bucket[i];
    while(old_hash) {
      tmp=old_hash;
      old_hash=old_hash->next;
      h=hash_string(tptr, tmp->key);
      tmp->next=tptr->bucket[h];
      tptr->bucket[h]=tmp;
      tptr->entries++;
    } /* while */
  } /* for */

  /* free memory used by old table */
  free(old_bucket);

  return;
}

/*
 *  hash_string_init() - Initialize a new hash table.
 *
 *  tptr: Pointer to the hash table to initialize
 *  buckets: The number of initial buckets to create
 */
void hash_string_init(hash_string_t *tptr, int buckets) {

  /* make sure we allocate something */
  if (buckets==0)
    buckets=16;

  /* initialize the table */
  tptr->entries=0;
  tptr->size=2;
  tptr->mask=1;
  tptr->downshift=29;

  /* ensure buckets is a power of 2 */
  while (tptr->size<buckets) {
    tptr->size<<=1;
    tptr->mask=(tptr->mask<<1)+1;
    tptr->downshift--;
  } /* while */

  /* allocate memory for table */
  tptr->bucket=(hash_string_node_t **) malloc(tptr->size * sizeof(hash_string_node_t *));
  memset(tptr->bucket,0,tptr->size * sizeof(hash_string_node_t *));

  pthread_mutex_init(&tptr->mutex,NULL);
  
  return;
}

void* hash_string_lookup(hash_string_t *tptr, const char *key) {
  int h;
  hash_string_node_t *node;
  L;
  h=hash_string(tptr, key);
  for (node=tptr->bucket[h]; node!=NULL; node=node->next) {
    if (!strcmp(node->key, key))
	{
		UL;
      	return node->data;
	}
  }
	UL;
  return NULL;
}

hash_string_node_t* hash_string_insert(hash_string_t *tptr, const char *key, void* data) {
  hash_string_node_t *node;
  int h;
	L;
	h=hash_string(tptr, key);
	for (node=tptr->bucket[h]; node!=NULL; node=node->next) {
	if (strcmp(node->key, key)==0)
	{
		UL;
	  return NULL;
	}
	}

	/* expand the table if needed */
  while (tptr->entries>=HASH_FUNC_LIMIT*tptr->size)
	  rebuild_func_table(tptr);

  /* insert the new entry */
  h=hash_string(tptr, key);
  node=(struct hash_string_node_t *) malloc(sizeof(hash_string_node_t));

  node->data=data;
  node->key=malloc(strlen(key)+1);
  memset(node->key,0,strlen(key)+1);
  strcpy(node->key,key);
  node->next=tptr->bucket[h];
  tptr->bucket[h]=node;
  tptr->entries++;
  UL;
  return node;
}

/*
 *  hash_string_delete() - Remove an entry from a hash table and return a pointer
 *  to its data or HASH_FUNC_FAIL if it wasn't found.
 *
 *  tptr: A pointer to the hash table
 *  key: The key to remove from the hash table
 */
void* hash_string_delete(hash_string_t *tptr, const char *key) {
  hash_string_node_t *node, *last;
  void* data;
  int h;

  /* find the node to remove */
	L;
  h=hash_string(tptr, key);
  for (node=tptr->bucket[h]; node; node=node->next) {
    if (!strcmp(node->key, key))
      break;
  }

  /* Didn't find anything, return HASH_FUNC_FAIL */
  if (node==NULL)
  {
	  UL;
    return HASH_FUNC_FAIL;
  }
  /* if node is at head of bucket, we have it easy */
  if (node==tptr->bucket[h])
    tptr->bucket[h]=node->next;
  else {
    /* find the node before the node we want to remove */
    for (last=tptr->bucket[h]; last && last->next; last=last->next) {
      if (last->next==node)
        break;
    }
    last->next=node->next;
  }
  UL;
  /* free memory and return the data */
  data=node->data;
  free(node->key);
  free(node);

  return(data);
}

/*
 * hash_string_destroy() - Delete the entire table, and all remaining entries.
 * 
 */
void hash_string_destroy(hash_string_t *tptr) {
  hash_string_node_t *node, *last;
  int i;

  for (i=0; i<tptr->size; i++) {
    node = tptr->bucket[i];
    while (node != NULL) { 
      last = node;   
      node = node->next;
	  free(last->key);
      free(last);
    }
  }     

  /* free the entire array of buckets */
  if (tptr->bucket != NULL) {
    free(tptr->bucket);
    memset(tptr, 0, sizeof(hash_string_t));
  }
}

void hash_string_destroy_cleanup(hash_string_t *tptr, void(*cleanup_func)(void*)) {
  hash_string_node_t *node, *last;
  int i;
	
  for (i=0; i<tptr->size; i++) {
    node = tptr->bucket[i];
    while (node != NULL) { 
      last = node;
	  cleanup_func(last->data);
	  node = node->next;
	  free(last->key);
      free(last);
    }
  }

  /* free the entire array of buckets */
  if (tptr->bucket != NULL) {
    free(tptr->bucket);
    memset(tptr, 0, sizeof(hash_string_t));
  }
}
